package com.algorithm.ch2.cjm.array;

import java.util.*;

/**
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * <p>
 * 示例:
 * <p>
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
 * 输出:
 * [
 *  ["ate","eat","tea"],
 *  ["nat","tan"],
 *  ["bat"]
 * ]
 * 说明：
 * <p>
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 *
 * @Author: Jie Ming Chen
 * @Date: 2019-01-09
 * @Version 1.0
 */
public class GroupAnagrams {

    public static void main(String[] args) {
        GroupAnagrams groupAnagrams = new GroupAnagrams();
        List<List<String>> lists = groupAnagrams.groupAnagrams1(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});

        System.out.println(lists.toString());
    }

    // leetcode 最优
    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String,Integer> map = new HashMap<>();
        List<List<String>> res = new ArrayList<>();
        int index = 0,count = 0;
        while(index < strs.length){
            char[] s = strs[index].toCharArray();
            Arrays.sort(s);
            String str = new String(s);
            if(map.containsKey(str)) {
                res.get(map.get(str)).add(strs[index]);
            } else {
                map.put(str,count);
                List<String> l = new ArrayList<>();
                l.add(strs[index]);
                res.add(l);
                count += 1;
            }
            index++;
        }
        return res;
    }

    // 转换成双map 206ms
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Map<Character, Integer>, List<String>> hashMap = new HashMap<>();

        for (String str : strs) {
            Map<Character, Integer> charMap = getHashMap(str.toCharArray());
            List<String> list = hashMap.get(charMap);
            if (list != null) {
                list.add(str);
                hashMap.put(charMap, list);
            } else {
                List<String> chList = new ArrayList<>();
                chList.add(str);
                hashMap.put(charMap, chList);
            }
        }

        List<List<String>> list = new ArrayList<>();
        list.addAll(hashMap.values());
        return list;
    }

    // 字符串换行成数组
    private Map<Character, Integer> getHashMap(char[] chars) {
        Map<Character, Integer> hashMap = new HashMap<>();
        for (char aChar : chars) {
            Integer integer = hashMap.get(aChar);
            if (integer != null) {
                hashMap.put(aChar, ++integer);
            } else {
                hashMap.put(aChar, 1);
            }
        }
        return hashMap;
    }
}
